As network communication and electronic commerce have been developed in the recent years, the ensuring of security in communication has been an important issue. One method of ensuring security is cryptography. Currently, communication has been actually done using various ciphers.
For example, a system has been put to practical use in which an encryption processing module is embedded in a small device, such as an IC card, and data transmission/reception is performed between the IC card and a reader/writer serving as a data-reading/writing device, thereby implementing authentication processing or encryption/decryption of transmission/reception data.
Various encryption processing algorithms are available. These encryption algorithms can be largely classified into public-key cryptography in which an encryption key and a decryption key are set as different keys, such as a public key and a secret key, and common-key cryptography in which an encryption key and a decryption key are set as a common key.
There are various algorithms for common-key cryptography. One algorithm involves generating a plurality of keys on the basis of a common key and repeatedly performing data transformation processing in units of blocks (e.g., 64 bits or 128 bits) using the generated keys. A typical algorithm employing such a key generation scheme and data transformation processing is a common-key blockcipher.
As typical common-key blockcipher algorithms, for example, a DES (Data Encryption Standard) algorithm, which was a standard cipher for the United States in the past, and an AES (Advanced Encryption Standard) algorithm, which is a standard cipher for the United States at present, are known.
These common-key blockcipher algorithms are mainly constituted of an encryption processing part including round-function executing parts that repeatedly perform transformation of input data, and a key scheduling part that generates round keys applied to respective rounds of the round-function parts. The key scheduling part generates an expanded key on the basis of a master key (main key) which is a secret key by increasing the number of bits, and, on the basis of the generated expanded key, generates round keys (sub-keys) to be applied to the respective round-function parts of the encryption processing part.
As a specific structure for executing such an algorithm, a structure that repeatedly executes a round function including a linear transformation part and a non-linear transformation part is known. For example, a Feistel structure is one typical structure. A Feistel structure has a structure that transforms plaintext into ciphertext by simply repeating a round function (F-function) serving as a data transformation function. In a round function (F-function), linear transformation processing and non-linear transformation processing are executed. Note that, as documents describing encryption processing using a Feistel structure, there are, for example, Non-Patent Document 1 and Non-Patent Document 2.
However, the common-key blockcipher has a problem of the leakage of keys due to cryptanalysis. The fact that the keys can be analyzed easily by cryptanalysis means that the cipher has low security, leading to a serious problem in applications.    Non-Patent Document 1: K. Nyberg, “Generalized Feistel networks”, ASIACRYPT '96, Springer Verlag, 1996, pp. 91-104.    Non-Patent Document 2: Yuliang Zheng, Tsutomu Matsumoto, Hideki Imai: On the Construction of Block Ciphers Provably Secure and Not Relying on Any Unproved Hypotheses. CRYPTO 1989: 461-480